#include<stdio.h>
#include<stdlib.h>
#define NULL (void*)0

#define Balanced(x) (stature((x).leftchild) == stature((x).rightchild))  // 理想平衡条件
#define BalFac(x)  (stature((x).leftchild) - stature((x).rightchild))   //平衡因子
#define  AvlBalanced(x)  ((-2<BalFac(x)&& (BalFac(x))<2))  // AVL平衡条件


#define HasLChild(x)  ((x).leftchild)  // 是否有左孩子
#define HasRChild(x)  ((x).rightchild)
#define HasParent(x)   ((x).parent)

//#define IsLChild(x) ((x)->parent->leftchild == (x)?1:0)//x pointer
//#define IsRChild(x) ((x)->parent->rightchild == (x)?1:0)//x pointer


#define FromParentTo(x)  (IsLChild(x)?(x)->parent->leftchild:(x)->parent->rightchild)  //x pointer

#define stature(p)  ((p)?(p)->height:-1)
typedef enum {RB_RED , RB_BLACK} RBColor;


int max(int a,int b)
{
    return a>b?a:b;
}
typedef struct BinNode_Tree
{
    int elem;
    struct BinNode_Tree*  parent;
    struct BinNode_Tree* leftchild;
    struct BinNode_Tree* rightchild;
    int height;  //高度通用
    int npl; //NULL Path Length
    RBColor color ;//颜色

}BinNode;

int IsLChild(BinNode* x)
{
    if(x->parent)
    {
        if(x->parent->leftchild == x)
            return 1;
        else
            return 0;
    }
    return 0;

}

int IsRChild(BinNode* x)
{
    if(x->parent)
    {
        if(x->parent->rightchild == x)
            return 1;
        else
            return 0;
    }
    return 0;

}
int  updateHeight (BinNode* x)
{
    return x->height = 1 + max(stature(x->leftchild),stature(x->rightchild));

}

void updateHeightAbove(BinNode * x)
{
    while (x)
    {
        updateHeight(x);
        x = x->parent;
    }

}

//默认的创建方式
//     new_node->height = 0;
//     new_node->npl = 1;
//     new_node->color = RB_RED;
BinNode* BinNode_Create(int x)
{
    BinNode* new_node = (BinNode *) malloc(sizeof(BinNode));
    new_node->elem = x;
    new_node->height = 0;
    new_node->npl = 1;
    new_node->color = RB_RED;
    new_node ->parent =0;
    new_node->leftchild=0;
    new_node->rightchild =0;
    return new_node;

}
//把 x 插入 s的 左节点   ，并且更新全数高度
BinNode * insertAsLC(BinNode * s,int x)
{
    BinNode* new_node = BinNode_Create(x);
    new_node->parent = s;
    s->leftchild = new_node;
    updateHeightAbove(new_node);

}

BinNode * insertAsRC(BinNode * s,int x)
{
    BinNode* new_node = BinNode_Create(x);
    new_node->parent = s;
    s->rightchild = new_node;
    updateHeightAbove(new_node);

}

//t作为s 节点的左子节点插入
//并且 更新节点的高度
void insertAsLeftTree(BinNode * s,BinNode *t)
{
    s->leftchild = t;
    t->parent = s;
    updateHeightAbove(t);
}

//t作为s 节点的右子节点插入
//并且 更新节点的高度
void insertAsRightTree(BinNode * s,BinNode *t)
{
    s->rightchild = t;
    t->parent = s;
    updateHeightAbove(t);
}

BinNode* succ_In(BinNode * s)  //s在中序遍历下的直接后继
{
    BinNode* temp = 0;
    if(HasRChild(*s))  //如果S有右子树 ，，s的直接后继就是 右子树 的最左节点
    {
        temp = s->rightchild;
        BinNode * res = temp;
        while (temp)
        {
            res = temp;
            temp = temp->leftchild;
        }
        return res;
    }

    while (HasParent(*s))
    {
        if (IsLChild(s))
        {
            return s->parent;
        }
        if (IsRChild(s))
        {
            s= s->parent;
        }
    }
    return  (BinNode*)0;
}

typedef struct AVLTree
{
    BinNode * _root;
    BinNode * _hot;
    int _size;
}AVLTree;

AVLTree *AVLTree_Create()
{
    AVLTree * avl = (AVLTree*) malloc(sizeof(AVLTree));
    avl->_hot =0;
    avl->_root =0;
    avl->_size =0;
}

BinNode *  AVLTree_Search(AVLTree * tree,int e);

void AVLTree_Insert(AVLTree * tree, int e);

void AVLTree_Delete(AVLTree * tree, int e);

void solveBalance(AVLTree *tree,BinNode * v);

/*
AVLTree_Search
    查找成功 : 则返回 成功处所在结点
    查找失败 : 则返回 NULL，_hot 变量指向NULL的上一个结点
*/
BinNode * AVLTree_Search(AVLTree * tree,int e)
{
    tree->_hot =NULL;
    BinNode * v = tree->_root;
    while (v)
    {
        if(v ->elem == e)
            return v;
        if(v->elem <e)
        {
            tree->_hot =v;
            v =v->rightchild;
        }
        else
        {
            tree->_hot =v;
            v =v->leftchild;
        }
    }
    return NULL;


}
void AVLTree_Insert(AVLTree * tree, int e)
{
    if(tree->_root ==0)  //首次插入
    {
        tree->_root  = BinNode_Create(e);
        return;

    }
    BinNode * v = AVLTree_Search(tree,e);  //先在tree中查找e
    if(v)           //查找成功，不插入
        return;
    v = tree->_hot; //查找,v必然是NULL，_hot是其父节点
    BinNode* newNode = BinNode_Create(e);
    if(v->elem<newNode->elem)  //作为右孩子插入
    {
        v->rightchild = newNode;
        newNode->parent =v;
    }
    else                       //作为左孩子插入
    {
        v->leftchild = newNode;
        newNode->parent =v;
    }
    solveBalance(tree,v);

}
/*

*/
BinNode * rightRotate(BinNode * node)
{
    int isleft = 0;

    if(IsLChild(node)) isleft =1;

    BinNode * p = node->parent;
    BinNode * C = node->leftchild;
    BinNode * CL = C->leftchild;
    BinNode * CR = C->rightchild;

    node->leftchild = CR;
    if(CR)
        CR->parent =node;

    C->rightchild = node;
    node->parent = C;
    if(C)
        C->parent = p;
    if(p)
    {
        if(isleft)
        {
            p->leftchild =C;
        }
        else
        {
            p->rightchild =C;
        }

    }
    updateHeight(node);
    updateHeight(C);
    return C;
}

BinNode *  leftRotate(BinNode * node)
{
    int isleft = 0;

    if(IsLChild(node)) isleft =1;

    BinNode * p = node->parent;
    BinNode * C = node->rightchild;
    BinNode * CL = C->leftchild;
    BinNode * CR = C->rightchild;

    node->rightchild = CL;
    if(CL)
        CL->parent =node;

    C->leftchild = node;
    node->parent = C;
    if(C)
        C->parent = p;

    if(p)
    {
        if(isleft)
        {
            p->leftchild =C;
        }
        else
        {
            p->rightchild =C;
        }

    }
    updateHeight(node);
    updateHeight(C);
    return C;

}
void solveBalance(AVLTree *tree,BinNode * v)
{
    while (v)
    {
        printf("In loop\n");
        printf("v value :%d",v->elem);
        if(AvlBalanced(*v)) //若该节点平衡，则向上 走
        {
            updateHeight(v);
            v = v->parent;
        }
        else  //若节点失衡，则有四种情况
        {

            BinNode *parent = v->parent;
            BinNode * currentNode =0;
            BinNode * child,*grandchild;
            if(stature((v->leftchild)) > stature((v->rightchild)))
            {
                child = v->leftchild;
                if(stature(child->leftchild)>stature(child->rightchild))
                {

                    /*              p                           p
                                    v                           c
                                c      vr       ====》     gc          v
                            gc    cr                 gcl       gcr  cr   vr
                        gcl   gcr
                    */
                    //grandchild = child->leftchild;
                    currentNode = rightRotate(v);

                }
                else
                {
                        /*          p                           p
                                    v                           gc
                                c      vr       ====》     c          v
                            cl    gc                     cl  gcl    gcr   vr
                              gcl   gcr
                    */
                    leftRotate(child);
                    currentNode = rightRotate(v);

                }

            }
            else
            {
                child = v->rightchild;
                if(stature(child->leftchild)>stature(child->rightchild))
                {


                    rightRotate(child);
                    currentNode = leftRotate(v);

                }
                else
                {
                    printf("zag zag\n");

                    currentNode = leftRotate(v);
                    printf("zag zag done\n");
                }
            }

            if(parent == NULL)
            {
                tree->_root = currentNode;
            }
            v=parent;
        }

    }

}
void PreOrder(BinNode * node)
{
    if(!node)
        return;
    printf("%d ",node->elem);
    PreOrder(node->leftchild);

    PreOrder(node->rightchild);
}
int main()
{
    AVLTree * avl = AVLTree_Create();
    AVLTree_Insert(avl,1);
    PreOrder(avl->_root);
    printf("\n");
    AVLTree_Insert(avl,2);
    PreOrder(avl->_root);
    AVLTree_Insert(avl,3);
    PreOrder(avl->_root);
    AVLTree_Insert(avl,4);
    printf("\n");
    PreOrder(avl->_root);
    AVLTree_Insert(avl,5);
    printf("\n");
    PreOrder(avl->_root);
    return 0;

}